package com.jack.leetcode.eachproblem_2020;

public class 最大间距 {

    public int maximumGap(int[] nums) {
        if(nums == null || nums.length < 2){
            return 0;
        }
        quickSort(nums, 0, nums.length - 1);
        int max = 0;
        for(int i = 0;i < nums.length - 1;i++){
            max = Math.max(nums[i + 1] - nums[i], max);
        }
        return max;
    }

    private void quickSort(int[] nums, int begin, int end){
        if(begin > end){
            return;
        }
        int i = begin, j = end, num = nums[begin];
        while(i < j){
            while(i < j && nums[j] > num){
                j--;
            }
            if(i < j){
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] < num){
                i++;
            }
            if(i < j){
                nums[j--] = nums[i];
            }
        }
        nums[i] = num;
        quickSort(nums, begin, i - 1);
        quickSort(nums, i + 1, end);
    }
}
